The prerequisite for practicable program analysis is the identification of the individual procedures, which correspond to individual stack frames. We present how machine learning techniques can be used in the setting of program analysis in order to find these stack frames. This combination of machine learning and abstract interpretation-based analysis provides the first fully automatic analysis framework for executables. Our approach can also be applied to identify library functions or malicious behaviour in a given piece of assembly.

In this article we provide an interprocedural analysis of linear two-variable equalities. The novel algorithm has a worst-case complexity of 𝒪( n ⋅ k 4 ), where k is the number of variables and n is the program size. Thus, it saves a factor of k 4 in comparison to a related algorithm based on full linear algebra. We also indicate how the practical runtime can be further reduced significantly. The analysis can be applied, for example, for register coalescing, for identifying local variables and thus for interprocedurally observing stack pointer modifications as well as for an analysis of array index expressions, when analyzing low-level code.