Fixed-Point Analysis for ARA: Best Value for Pointers

ARA is a whole-system compiler to optimizes the system with global knowledge. It consists of two parts. In a first step it takes a (real-time) system's source code as input and statically analyzes it to retrieve global knowledge. Equipped with this knowledge, it then synthesize an optimized system image in a second step. Possible optimizations are speed or memory usage improvements. ARA focuses on usage and interactions between application and underlying operating system.

One part of the ARA's analysis is a value flow analysis (mainly to retrieve system call arguments). Currently, it uses the SVF framework for this but invokes it as single pass. The analysis is especially imprecise for function pointers, since the SVF must resolve them (retrieving their values) before it can follow them. See for example this code:

int ptr_func(int a, int c) { return a; }
int ptr_func2(int a, int c) { return c; }
typedef int (*PtrFunc)(int, int);

int main() {
    PtrFunc func = ptr_func2;
    int duration = func(3, 5);
    syscall(duration);
}

To resolve the value of duration, the analysis must resolve the value of func first. For best results, this requires multiple iterations of the value analysis, until a fixed point is reached (no further values are found).

The goal of this thesis is to extend ARA to do such a fixed-point value analysis with the SVF and extend the analysis to function pointers, conditions and loops.

Topics covered by this thesis:
static analysis, value analysis, LLVM, C++, Python

Further Reading

SVF website: http://svf-tools.github.io/SVF/

OSPERT Workshop B
ARA: Automatic Instance-Level Analysis in Real-Time Systems
Gerion Entrup, Benedikt Steinmeier, Christian DietrichProceedings of the 15th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT '19)2019.
PDF [BibTex]
OSPERT Workshop B Best Paper Award
Levels of Specialization in Real-Time Operating Systems
Björn Fiedler, Gerion Entrup, Christian Dietrich, Daniel LohmannProceedings of the 14th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT '18)2018Best Paper Award.
PDF [BibTex]