Graph models of memory access traces

Abstract

This paper describes proposal of a method to analyse memory access traces of a process. It is based on record of all addresses which a process generates by memory access during its run time. The process address trace is subsequently represented by a graph structure suitable for further analysis by a variety of available graph and network tools. Preliminary results proved such approach to be useful when detecting whether dynamical linking was used by a process.

Keywords

• eol>memory address trace
• graph representation
• graph invariant
• strongly connected component

1. Introduction

While executing a program, processor makes at least one memory access to fetch each instruction and additional access to load or store a data is possible. It is a well known that a sequence of all addresses accessed by a process does not have a uniform distribution. Rather it exhibits various patterns, which were recognised and studied in 1970s by Denning [ 1 ]. 1.1. Locality principles process. In our work we use Intel’s binary PIN tool [ 5 ], which by means of code instrumentation and various plug-in modules allows to record information about each memory access that a process makes. Particularly, modules pinatrace and itrace executes call-back function which might record the address of instruction, load or store access type, and the address of memory operand if any. Further modification of the modules allows to store to a separate output files also the binary code of the instruction or the mappings of memory regions used by the process.

The basic patterns are known as principles of locality [ 2 ], namely sequential, spatial and time locality. On the 2.1. Graph representation one hand, these principles are natural consequences of The main output file contains sequence of all addresses how processors execute instructions, how processes use accessed by a process in the text hexadecimal form, one a stack for passing arguments and storing local variables, per line. Thus in a raw form the file might get too large or how algorithms process a data in general. On the other and hard to manipulate. We conjecture, that essential hand, locality in address sequences allows to construct information is contained in the graph structure, which highly eficient memory systems, which is very eficient can be constructed by assigning a vertex to each unique while the fastest memory, registers, are expensive and address and connecting two vertices by a directed edge, scarce and high volume memory storage is relatively whenever the two addresses lies on consecutive lines. slow. This is because an average process, a typical useful Vertices of such graph can be labelled by the address, algorithm, does not need all its data at once. Exploita- edges can be labeled by the number of occurrences of tion of patterns in memory access led to development of a corresponding address pair. As a typical program is demand paging [ 3 ], [ 4 ], utilisation of data prefetching or also comprised of loops, the labeled graph representation LRU (Least recently used) data replacement algorithm on can be (at least in principle) smaller than the complete various hierarchy levels, e.g. cache lines, memory pages, address trace. Although the original addresses might be disk blocks. useful when analysing execution of particular process, the graph structure itself can represent some more gen2. Address trace recording eral properties of the program. Moreover, the addresses can change in each run of the same program due to security measures imposed by operating systems, for example ASLR (Address space layout randomisation).

Emulation and virtualisation provide several possibilities of recording partial or complete address trace of a

2.2. Graph properties

Without lost of information, further reduction of the graph can be achieved by squeezing a sequence of equidistant addresses to a block designated by only the first and the last address of the sequence. These blocks are called All programs tested in [ 7 ] contained several singlebasic blocks Sequence is, of course, the very basic pro- ton strongly connected components and one component gramming construct present in any program. However, containing rest of the vertices in the trace graphs for a sequence of instructions need not to generate accesses data memory access. For the instruction addresses, the to consecutive memory addresses. Moreover, this prop- structure was similar, but apart from one big compoerty depends on the processor architecture. Processors nent there were always components composed of 37, of CISC types may have variable instruction size, so they 31, and 10 vertices. Using the additional stored inforcan yield subsequent instruction addresses distances from mation about memory region mappings (it is found in one to fifteen bytes (e.g. for Pentium based platforms). /proc/self/maps during run-time), as mentioned in RISC processors usually have fixed instruction code size, section 2, it was possible to identify the addresses with which creates a regular pattern of instruction sequences, the code of dynamical linker. Particularly, on an x86_64 as program counter register increments with each instruc- Linux system, the addresses belong to range mapped to tion except of branches. With RISCs, there are usually ifle ld-linux-x86-64.so.2. The experiment was reonly two instructions for data memory transfers (load- peated on an arm based Raspberry Pi system. The graph /store). All ALU operations are performed on registers structure looked very similar, it showed three strongly so data memory access might occur rarely. On the other connected components with orders 35, 28, 7. Addresses hand, a CISC type processor allows many instructions to forming these components belong to the range mapped operate on memory, thus addresses of instructions can to the file ld-2.28.so. All tested statically linked probe overlapped by data addresses more frequently. grams lack such structure. Thus it is possible to conclude

Processors from CISC family, notably there is only one that presence of the three strongly connected compomajor representative, the Intel compatible ones, allow for nents of this precise size determined by the platform, repeated execution of one single instruction, particularly means that the running process uses the dynamic linker. the string instructions, by means of so called instruc- Usually, using a dynamic linker for system utilities is a tion prefix ( rep repeating until CX register reaches zero, standard. Conversely, fake malicious programs pretendor alternatively, conditional variants REPZ/REPNZ check ing to be a legitimate utilities are often statically linked to also for other flags). This generates a special pattern all necessary libraries in order to minimise dependency of repeated single instruction address several times, so on target system. Thus missing the proper three concorresponding graph will comprise a loop edge on the nected components from the memory access graph can vertex with given instruction address. imply an attempt to exchange original program file with

All of these observations can be used to characterise a malware. Anyway, this can be considered a suspicious the architecture based on the graph properties only. condition and can serve as one of the inputs to a more complex security system (e.g. an IDS).

3. Trace analysis as security measure

Using memory traces for detection of program failures, like bufer overflows or other corruptions, or detection of malicious activity like directing control flow to area iflled with user provided data, is well established field of research, e.g. see [ 6 ]. In his bachelor thesis, M. Hluch [ 7 ] revealed that some property of the graph created from memory trace, particularly strongly connected components, always coincided with the way of linking which the program uses.

4. Conclusion

We described the procedure of creating directed graphs from complete memory address trace of a process. We conjecture that properties of this abstract structure – the graph, can indicate possible security risk. The main result is that presence of three strongly connected components of prescribed size is related to usage of a dynamic linker by the examined program. Absence of these strongly connected components thus may have implications for the security of the system.

3.1. Strongly connected components

Acknowledgments

As we mentioned above, the control flow of process in- This publication is the result of support under the duces an orientation on edges of the memory trace graph. Operational Program Integrated Infrastructure for the The graph is called strongly connected if there exists a project: Advancing University Capacity and Compepath between each pair of vertices, regarding the direc- tence in Research, Development a Innovation (ACCORD, tion of edges. A strongly connected component of graph ITMS2014+:313021X329), co-financed by the European is a maximal subgraph of which is strongly connected. Regional Development Fund.

References

[1] Peter J. Denning. The locality principle . Commun. ACM , 48 ( 7 ): 19 - 24 , July 2005 .

[2] Jefrey R. Spirn and Peter J. Denning . Experiments with program locality . In Proceedings of the December 5-7 , 1972 , Fall Joint Computer Conference, Part I , AFIPS ' 72 (Fall, part I ), page 611 - 621 , New York, NY, USA, 1972 . Association for Computing Machinery .

[3] Peter J. Denning. The working set model for program behavior . Communications of the ACM , 11 ( 5 ): 323 - 333 , 1968 .

[4] Andrew S. Tanenbaum . Operating Systems: Design and Implementation (Second Edition) . New Jersey: Prentice-Hall 1997 .

[5] Intel's web pages. Pin - A Dynamic Binary Instrumentation Tool , URL: https://www.intel. com/content/www/us/en/developer/articles/tool/ pin -a-dynamic-binary-instrumentation-tool .html, accessed on 2024- 07 -11.

[6] Zhixing Xu , Aarti Gupta , and Sharad Malik . Tracebased analysis of memory corruption malware attacks . In Ofer Strichman and Rachel Tzoref-Brill, editors, Hardware and Software: Verification and Testing , pages 67 - 82 , Cham, 2017 . Sprin- ger International Publishing.

[7] Matúš Hluch . Detekcia vzorov správania procesu v postupnosti adries. (Bachelor thesis supervised by D. Bernát .) Department of Computer Science. Faculty of Mathematics, Physics and Informatics . Comenius University, Bratislava, Slovakia. 2022 .