BF Memory Model
Memory bugs could be introduced at any of the following memory related processes: address formation, allocation, use, and deallocation. The BF Memory Bugs Model helps identify where in these processes bugs could occur (Fig. 1). The processes are named after the BF memory bugs classes: MAD, MAL, MUS, and MDL, which cover bugs in addressing, allocation, use, and deallocation.
Each of the memory related processes involves one or more memory operations. Each memory operation is over a piece of memory or over the address needed to reach it. That memory is used for storing data and has an important property: it is finite. It has boundaries; it has size. This piece of memory with well-defined size is called an object (or a little object – not Object like in Object Oriented Programming, OOP). At least one variable in source code should hold this address, otherwise the object will be unreachable. It is called an owner and could be a pointer or a reference. A pointer is an owner that is loosely connected to an object. It is a variable that holds a memory address. Pointers can be reassigned and repositioned. They can point to an object in any memory location (e.g. stack, heap, .bss). A reference is an owner that is tightly connected to an object. It cannot be reassigned or repositioned.
The lifecycle of an object comprises four steps, corresponding to the allocation, address formation, use, and deallocation processes: First, some memory is reserved – an object is created. Also, its address should be known – an owner is created and the object’s address is assigned to it. Then, some data is written to the object or read from it through the owner – the object is in use. Last, the reserved memory is released through the owner – the object is destroyed.
The model clearly shows that the MAD, MAL, MUS, and MDL processes do not overlap in operations and inputs.
Memory Addressing Operations
The operations related to Memory Addressing Bugs (MAD) are: Initialize, Reposition, and Reassign. They all concern forming or modifying the owner’s value. Initialize is the very first assign of an object address to an owner (pointer or reference); it also positions the owner at the start of the object. Missing initialization of a pointer or a reference is a common memory addressing bug. Bugs in owner initialization could leave it pointing to a meaningless object. Reposition changes the value of an owner to another position inside its object – e.g., to access different array elements. The new position is calculated via incrementing (++) or decrementing (--) the pointer, or via other pointer arithmetic. Moving an owner via a bugged Reposition operation could get it pointing outside the object bounds. Reassign changes the ownership to a different object. Bugs in Reassign could disconnect an owner from its object, which usually leads to Memory Use Bugs (MUS) or Memory Deallocation Bugs (MDL). Note that Fig. 1 depicts an one-object model, this is why there are no arrows from Reassign to MUS and MAL. Reassign is valid only for pointers; it is not valid for references.
Memory Allocation Operations
The operations related to Memory Allocation Bugs (MAL) are: Allocate, Extend, and Reallocate. They concern creating or extending an object.Allocate reserves space in memory for an object; it also defines its initial boundaries and size. Allocation bugs could happen in a run time routine such as malloc() or in an OOP operator such as new. Memory reserved at compile–time is also an Allocate operation from the BF point of view. Extend allocates additional memory for an object in the same space and redefines its boundaries and size. Reallocate, in terms of MAL, allocates a new larger piece of memory at a new address, copies the object content there, reassigns the owner, and deallocates the previous piece of memory. An object size increase through a bugged reallocation could leave an owner pointing to deallocated memory (dangling pointer) or could free already deallocated memory (double free). Bugs in Reallocate may concern multiple owners of the same object. Also, a reallocation routine could return a NULL pointer if no memory is available. The MAL operations affect the boundaries and the size of an object.
Memory Use Operations
The operations related to Memory Use Bugs (MUS) are: Initialize, Read, Write, Clear, and Dereference. They concern reading or writing the content of an object through one of its owners. Initialize is the very first write into an object, after it is allocated. Missing initialization of an object is a common memory use bug. Bugs in object initialization could lead to use of random or malicious data. Read gets content from an object. Write puts content into an object. Bugs in Read or Write endup in reading or writing outside the boundaries of the object. Clear is the very last write into an object, before it is deallocated. It assures the memory of an object no longer has meaningless values and information would not be exposed when new owners get pointed to it. Clearing is critical for objects storing sensitive data. Bugs in Clear could leak confidential information such as passwords and cryptographic private keys. Dereference overreaches Initialize, Read, Write, and Clear, focusing on the accesses of an object no matter if it is for reading or for writing. It relates to the term “pointer dereference.” Bugs in Dereference are practically unsuccessful reading or unsuccessful writing.
Memory Deallocation Operations
The operations related to Memory Deallocation Bugs (MDL): Deallocate, Reduce, and Reallocate. They concern destroying or reducing an object through one of its owners. Deallocate releases the allocated memory of an object. Deallocation bugs could happen in a run time routine such as free() or in an OOP operator such as del. Memory released when a variable gets out of scope is also Deallocate operation from the BF point of view. Reduce deallocates part of the object memory and redefines its boundaries and size. Reallocate, in terms of MDL, allocates a new smaller space
in memory at a new address, copies part of the object content there, reassigns the owner, and deallocates the previous piece of memory. An object size decrease through bugged reallocation could lead to dangling pointers and also could cause double free. Reallocate bugs may concern multiple owners of the same object. Also, a reallocation routine could return a NULL pointer if there is no memory available. The MDL operations affect the boundaries and the size of an object.
The BF Memory Bugs Model
The following figure presents our BF randomness bugs model, it comprises the MAD, MAL, MUS, MDL processes, which do not overlap in operations and inputs. Shows the Memory operations flow. MAD covers operations over an owner; MAL, MUS, and MDL cover operations over an object. Note that ”object” here is ”the little object” – a notion broader than OOP Object. MAL and MDL operations affect the boundaries and the size of an object. Blue arrows show the main flow. Green arrows show the flow for allocation at a specific address. Red arrows show the extra flow in case of reallocation.
BF Memory Bugs Model
- click on image for detailed view.
The BF Memory Bugs Model shows also the flow between the operations from different processes. The blue arrows show the main flow. The green arrows show the flow when allocation is requested at a specific address. The red arrows show the extra flow in case of reallocation.
Following the blue arrows, starting from the upper left corner on Fig.1, the very first operation in the lifecycle of an object is: MAL Allocate an object. Following the green arrows, the first operation is MAD Initialize an owner. In the former case, next operation should be MAD Initialize the owner to the address returned by the Allocate operation. In the latter case, next operation should be: MAL Allocate an object at the address the owner holds. After an object is allocated and its owner is initialized, it can be used via the operations: MUS Read or MUS Write. The boundaries and the size of an object are set at allocation, then they can be changed (shown with dashed arrows on Fig. 1) by any MAL or MDL operation. If there are more than one owner of an object, Reallocate (in MAL or MDL) should be followed by Reposition over all these owners. A Deallocate an object operation should properly be followed by Reassign of all its owners to either NULL or another object.