How to create a restricted language that allows sound and complete point-to analysis?
If we can revise the foundamental elements of a system, so that we can use a totally different memory model in the architecture, languages, and OS, can we make pointer-to analysis a decidable and polynomial problem?
malloc-like mechanisms from the memory model while keeping the memory being dynamically available for program to use?malloc-like mechanisms so that every pointer’s property can be statically checked before execution?Reference 1 GeorgiaTech SS Lab: https://gts3.org/pages/projects.html System software commonly uses indirect calls to realize dynamic program behaviors. However, indirect-calls also bring challenges to constructing a precise control-flow graph that is a standard prerequisite for many static program-analysis and system-hardening techniques. Unfortunately, indentifying indirect-call targets is a hard problem. In particular, modern compilers do not identify indirect-call targets by default. Existing approaches identify indirect-call targets based on type analysis that matches the type of function pointers and the ones of address-taken functions.
Reference 1 Escape Capture References: Escape Analysis & Capture Tracking in LLVM Pointer Capture: A pointer value is captured if the function makes a copy of any part of the pointer that outlives the call. Pinter Escape: A pointer value escapes if it is accessible from outside the current function or thread. The latter case is sometimes considered separate and called thread-escape. Capture and Escape are not opposites: Informally, escaping is concerned with the contents of the pointer, while capturing is concerned with the pointer itself 1.
Reference 1 AppContext: Differentiating Malicious and Benign Mobile App Behaviors Using Context. ICSE. 2015. ↩
Q & A How many incomplete nodes during evaluation? Ans: Not much, but most program exists. Including the collapsed nodes, ranging from 1.2% ~ 88.5%. See evaluation: type inference result Basics Flow sensitive1: takes into account the order of statements in a program. Path Sensitive: takes into account the branch conditions. Context Sensitive: names objects by entire acyclic call paths. A callee will return to its single call site instead of all possible call sites.
References: Pointer Analysis: Haven’t we solved this problem yet? By Micheal Hind, IBM. PASTE, 2001. Wiki: Program Analysis: https://en.wikipedia.org/wiki/Program_analysis Undecidability References: Pointer Analysis The undecidability of aliasing More Multi-layer Type Analysis Reference 1 C++ and Casting Pointer to virtual function tables is frequently cast to general types such as char*, rendering the type match ineffective. MLTA: a mechanism to precisely connect VTables to the corresponding classes and to keep track of class casting.
If you could revise
the fundmental principles of
computer system design
to improve security...
... what would you change?