Methods and Means of Searching Errors When Working With Dynamic Memory

Abstract

The subject The work discusses methods and means of nding errors when working with dynamic memory that arise as a result of exploiting vulnerabilities in implementations of dynamic memory allocation algorithms in the C language - allocators. Such vulnerabilities are common for software systems of various levels and purposes, including system software. Techniques for their operation are easily implemented, their descriptions are publicly available on the Internet, which explains their widespread use. The purpose of the work The goal is to develop an integrated approach and software that can detect vulnerabilities of dynamic memory allocators both at the compilation stage and during the operation of the software, issue appropriate warnings and recommendations, and also at the compilation stage, edit the code so that exploitation of vulnerabilities is impossible. One of the important quality criteria of the developed approach is the minimization of the overhead during the veri cation of software products. The method of the work Based on the studies and analysis of the exploitation techniques of the vulnerabilities Poisoned Null-byte, Overlapped Chunks, Fastbin Attack, Unsafe Unlink, House of Einherjar, House of Force, House of Spirit, House of Lore, Unsorted Bin Attack, a conclusion was drawn on the need for checking during the veri cation process software applications of the following conditions: { the possibilities of manipulating the elds of data structures that store service information, up to the creation of fake sections of the main memory on the heap or on the stack; { possibilities of accessing arbitrary sections of the computer memory due to intentional violation of the logic of the memory allocation algorithms. The analysis of modern veri cation methods and existing software products aimed at detecting vulnerabilities in the operation of memory allocation algorithms is carried out. Their advantages and disadvantages are

-

revealed. The results As a result of the work done, a software solution to the problem of detecting the potential exploitation of vulnerabilities of dynamic memory allocators in the form of a low-level debugger based on the method of symbolic execution of program code is proposed. 1

Introduction

The presence of vulnerabilities in the operation of dynamic memory allocation algorithms can lead to loss and/or intentional data corruption and, among other negative consequences, to property damage. Obviously, the detection of appropriate errors in the program code is necessary to minimize unwanted e ects and their misuse. Therefore, the development of strategies for the automatic detection of such errors within the life cycle of software and products based on them is an urgent task. 2

Vulnerabilities in the realization of the algorithms of dynamic memory allocation

The basic concepts of dynamic memory allocation in C [ 1 ] are the following. Each thread is assigned with some memory area { \arena" in which the memory chunks will be allocated and freed upon application requests. Each arena is owned by one or more heaps consist of chunks, and a new heap is allocated with full use of the previous heap. "Malloc state" - (the arena header, is a structure from which the memory for storing the initial heap for this arena is usually taken) stores information about bins (linked lists of chunks in the heap), top chunk (a chunk on the upper memory boundary requested from the OS) and so on. The heap is described by a structure called \heap info", which stores pointers to its arena, previous heap, etc. Chunk (the \malloc chunk" structure) is the range of memory on the heap allocated to the application. It can be combined with other chunks to get a larger chunk if needed. The metadata for the allocated and free chunks are di erent. Free chunks are stored in singly connected or doubly connected lists { i.e. bins. There are: { 10 of fastbin bins. They store chunks ranging in size from 32 to 160 bytes.

The fastbin list works on the principle of LIFO (Last Input First Output). { 64 of smallbin bins. They store chunks smaller than 1024 bytes. Each bin gets chunks of the appropriate size. Smallbins are based on the FIFO principle (First Input First Output). { 63 of largebin bins. They store chunks larger than 1024 bytes. Largebin chunks are stored in descending order of size.

{ 1 unsorted bin - all released chunks get into it.

When malloc is called, chunks are retrieved from the unsorted bin and transferred to the commensurate bins, or returned to the user. All beans are stored in the malloc state structure.

The glibc library implements algorithms for e cient work with memory. The requested chunks, depending on the size, are extracted from di erent bins in the order established by the corresponding algorithms of the glibc library. At present, there is a set of known vulnerabilities in the realization of the algorithms of dynamic memory allocation in the glibc library, which are considered on the Internet sites [ 2,3 ] and are illustrated with detailed examples [ 4 ]. As can be seen from table 1, glibc developers introduced patches that make it impossible to conduct a number of attacks, including a patch was proposed in 2017 to combat overwriting metadata in a single byte of the heap: https://sourceware.org/ml/libcalpha/2017-10/msg00773.html. Table 1 shows a comparison between versions 2.25 and 2.26 of the glibc library, depending on the presence of vulnerabilities listed in the rst row of the table.

According to the CWE (Common Weakness Enumeration) classi cation [ 5 ], the list of attacks in table 1 exploits vulnerabilities that fall into the following categories: 1. CWE-122 Heap-based Bu er Over ow 2. CWE-415 Double Free 3. CWE-416 Use after free 4. CWE-476 NULL Pointer Dereference

If we classify the presented vulnerabilities according to the technique of use, the main list can be presented in the following edition (table 2) depending on: { attacker's capabilities to overwrite top chunk (see heap organization in glibc) and elds: prev size, size, fd, bk; { the ability to create a special \fake" chunk on the stack or heap; { from the presence of \double free" vulnerability; { from the ability to free a pointer to an arbitrary address ("arbitrary free").

Let us illustrate the undesirable behavior of programs(table 3) due to the use for example of the Overlapped chunks and Fastbin Attack techniques, based on some of the vulnerabilities like CWE-415.

In the rst column of table 3 the code of the rst example is placed. In this example after deliberately recording an invalid value of the size of chunk p2 and releasing this chunk if a new memory chunk (p6) is allocated in its place, the e ect of overlapping two chunks (p3 and p6) appears, which clearly demonstrates the output of the program placed under the code. The second example demonstrates the usage of the double free vulnerability: the chunk p1 is released twice and entered in a fastbin. After that the rewriting in its eld fd of the position of "stack var" variable allows one after the new calling of malloc to return the chunk (pp4) to an arbitrary address, in this case, at address "8 + (char *) & stack var", which is re ected in the output of the program.

It is obvious the occurrence of similar situations during the software operation is unacceptable and leads to the inevitable search for solutions to the problem of automatization of the ght against the considered phenomena at all stages of the software life cycle. 3

Existed approaches and solutions

At presence there are a number of approaches to solving the problem, among which, as the most promising, we can distinguish the following: fuzzing method, dynamic analysis approach, model checking approach, symbolic execution approach, Binary Decision Diagrams application and SAT task solution.

It should be noted that the use of each of the methods implies the overhead of the execution of the program, which in some cases can be up to 500%. Let us consider in more detail some of them.

In [ 6 ] and [ 7 ], the use of \smart" fuzzing to search for bu er over ow vulnerabilities was proposed. Here, fuzzing is understood as an approach in which, instead of the expected input data, random or specially generated data is transmitted to the program. The objects of interest are crashes and freezes, violations of internal logic and checks in the application code, memory leaks.

Dynamic analysis is one of the code veri cation methods and is performed during program execution. The disadvantages of this approach are the impossibility of checking all the ways the program can be executed and the slowdown of the program due to the parallel execution of dynamic analysis.

In [ 8 ], a veri cation method is considered using the created models of programs and algorithms (model checking). The speci cation for the program is written in the language of temporal logic, and then special algorithms automatically check whether the created model matches the speci cation.

An interesting approach is the symbolic execution of a program [ 9 ]. This technique of simulation execution of a program allows to represent some of the input variables used in the program in symbolic form. Such a symbol denotes the set of values of the input variable of the program from the scope of its de nition. Each symbolic execution is equivalent to executing a program on a set of speci c test values of input variables, which reduces the power of the set of necessary tests. Via symbolic execution approach, it is required to select input data on which an error will occur.

Since the task is relevant, today there are several products, such as CBMC, HAIT, Heap Hopper, ArcHeap and MOPS, dedicated to solving the problem.

CBMC is a veri er that provides the possibility of limited model checking (Bounded Model Checker) for the languages ANSI-C and C ++. It allows to verify over ow of the array (bu er over ow), pointers safety, exceptions, and user-speci ed assertions.

A tool called HAIT (Heap Analyzer with Input Tracing) [ 10 ] implements the approach of automatic collecting of the information about the state of the heap and the operations that are performed on it. The prototype is based on the Triton framework created for dynamic binary analysis of programs. HAIT logs memory operations and tagged values. Symbolic expressions are stored in the form of abstract syntax trees (AST), and the analysis of parsed tagged data is used to track memory operations a ected by user input.

Heap Hopper applies the principles of symbolic execution to search for bu er over ow vulnerabilities in the heap [ 11 ] . Heap Hopper is based on the Angr framework. At each step of the program execution, an object of the SimState class is created, which stores the state of the registers and memory of the program at the moment. Registers and memory can have a speci c or symbolic value. Each symbolic variable is represented as a class of BitVectorSymbol. It is also possible to manually mark the necessary input data as symbolic - it can be symbolic memory, represented as a SimSymbolicMemory class, or a symbolic le, represented by a SimFile class. When the conditional branch instruction is reached, a constraint on the symbolic variable is added. When calling the "malloc" operator with a symbolic parameter for the size of allocated memory, a memory chunk with symbolic metadata is created. At each step in the SimState class, the heap state is saved. The heap model presented in the Heap Hopper is considered approximate.

ArcHeap [ 12 ] is an automatic tool for detecting unexplored heap exploitation techniques, regardless of their realization. For its operation it is necessary to describe the parameters of the memory allocator as well as set of possible actions on the heap. During the study ArcHeap checks to see if combinations of these actions can potentially be used to perform maintenance techniques, such as random storage or overlapping chunks. As proof ArcHeap generates a PoC that demonstrates a discovered exploitation technique.

MOPS Modelchecking Programs for Security properties [ 13 ] - veri er of models extracted from the code of programs written in C. The correctness requirements are speci ed in a special form and correspond to the statements of the so-called \defensive" programming. During compilation, all possible execution paths are analyzed without regard to conditions. All possible tracks are collected. Of these, operators important to safety are highlighted. Having a context-free grammar of the C language, the program is presented as a pushdown automaton. The security model is represented as a nite-state machine that accepts a sequence of security operations. The sequence of security operators is \suitable" if it is received at the input by a state machine and puts it in a \safe" state.

Since only certain aspects of the task are implemented in all the presented products, the authors of this article consider it possible and expedient to search for a more comprehensive approach that would allow creating a product whose capabilities would include methods to detect the most complete list of vulnerabilities presented in program codes combined with possible overhead minimization for its implementation. 4

The proposed solution

It is known when verifying C / C ++ programs several scenarios are possible: { emulation of code execution in a virtual machine. { instrumentation of the executable le after the building and its execution on a real processor. { instrumentation of the program source code during compilation and subsequent execution of the le [ 14 ]. { performing changes to the source code of the program separately before compilation, for example, by facilities of the TXL language [ 15 ]. { the symbolic execution of the internal representation of the code during the compilation [ 16 ].

{ execution using the debugger after the building.

In addition, an important step is to obtain an abstract representation of register information. The most used are the internal representations of VEX and REIL. VEX uses an intermediate representation of SSA (Static single assignment), in which each variable is assigned a value only once.

The following comprehensive approach to solving the problem is proposed: dynamic symbolic (concolic - concrete and symbolic) execution of the executable le which combines the real execution of the program with symbolic execution should be carried out. Dynamic symbolic execution will allow to applicate techniques of program execution paths investigation and by adding security predicates to path constraints to check the potentially dangerous operations for real errors included in a program. To create a more precise representation of the heap during symbolic execution, it is proposed to work directly with the \malloc state" structure.

All the abilities and vulnerabilities from the table 1 should to be checked for each state of symbolic execution. This approach will allow to understand the applicability of attacks to errors while working with the dynamic memory.

In addition, in order to reduce overhead, instead of emulating, one should run the tested application by using a special debugger. In the future, it is also planned to investigate methods for nding errors in programs with interactive input. 5

Conclusion

The article examined the known techniques of attacks on dynamic memory, approaches to software veri cation, brie y characterized the existing solutions for nding errors in program code. A new approach to nding errors in memory allocators has been proposed. In the future, this approach is planned for implementation with subsequent comparison with existing solutions.

References

1. Understanding glibc malloc, https://sploitfun.wordpress.com/ 2015 /02/10/ understanding-glibc-malloc/comment-page- 1 /. Last accessed 25 May 2019

2. Yet another free() exploitation technique , http://phrack.org/issues/66/6.html. Last accessed 25 May 2019

3. Malloc Des-Male carum, http://www.phrack.org/issues/66/10.html. Last accessed 25 May 2019

4. A repository for learning various heap exploitation techniques , https://github. com/shellphish/how2heap. Last accessed 08 Nov 2019

5. Common Weakness Enumeration, https://cwe.mitre.org/index.html. Last accessed 25 May 2019

6. Bhardwaj , M. , Bawa , S. : Fuzz testing in stack-based bu er over ow . Advances in Intelligent Systems and Computing 759 , 23 { 36 ( 2019 )

7. Mouzarani , M. , Sadeghiyan , B. , Zolfaghari , M. A. : Smart Fuzzing Method for Detecting Heap-Based Bu er Over ow in Executable Codes . Proceedings - 2015 IEEE 21st Paci c Rim International Symposium on Dependable ( 2016 )

8. Karna , A.K. , Chen , Y. , Yu , H. , Zhong , H. , Zhao , J.: The role of model checking in software engineering . Frontiers of Computer Science 12 ( 4 ), 642 { 668 ( 2018 )

9. Dudina , I.A. , Belevantsev , A.A. : Using static symbolic execution to detect bu er over ows . Programming and Computer Software . 43 ( 5 ), 277 { 288 ( 2017 )

10. Atzeni , A. , Marcelli , A. , Muroni , F. , Squillero , G.: HAIT: Heap analyzer with input tracing . ICETE 2017 - Proceedings of the 14th International Joint Conference on e-Business and Telecommunications , 4 , pp. 327 { 334 . ( 2017 ).

11. Eckert , M. , Bianchi , A. , Wang R , Shoshitaishvili Y , Kruegel C , Vigna G.: Heap Hopper: Bringing Bounded Model Checking to Heap Implementation Security , 27th USENIX Security Symposium , 2018

12. Automatic Techniques to Systematically Discover New Heap Exploitation Primitives, https://arxiv.org/pdf/ 1903 .00503.pdf. Last accessed 25 May 2019

13. MOPS : an Infrastructure for Examining Security Properties of Software , http: //web.cs.iastate.edu/~hridesh/teaching/610/06/02/papers/mops-ccs02. pdf. Last accessed 25 May 2019

14. Jang , Y.-S. , Choi , J.-Y.: Automatic prevention of bu er over ow vulnerability using candidate code generation . IEICE Transactions on Information and Systems . E101D(12) , 3005 { 3018 ( 2018 )

15. Dahn , C. , Mancoridis , S.: Using program transformation to secure C programs against bu er over ows . Proceedings - Working Conference on Reverse Engineering , WCRE. 2003-January

16. Loding , H. , Peleska , J. Symbolic and Abstract Interpretation for C/C++ Programs / Electronic Notes in Theoretical Computer Science 217 ( 2008 ), https://www. sciencedirect.com/science/article/pii/S1571066108003885. Last accessed 25 May 2019