ctfnote
  • /home/ret2basic.eth
  • Game Hacking
    • ✅C++
    • Ghidra
    • Cheat Engine
    • Proxy
    • DLL injection
    • Keygen
    • Aimbot
  • Web3 Security Research
    • 👑Web3 Security Research Trivia
    • ✅Solidity
      • ✅Mastering Ethereum
      • ✅Storage
      • ✅Memory
      • ✅Calldata
      • ✅ABI
    • ✅Foundry
      • ✅Introduction
      • ✅How to Write Basic Tests
      • ✅Set Soliditiy Compiler Version
      • ✅Remappings
      • ✅Auto Format Code
      • ✅Console Log
      • ✅Authentication
      • ✅Error
      • ✅Event
      • ✅Time
      • ✅Send ETH
      • ✅Signature
      • ✅Fork
      • ✅Mint 1 Million DAI on Mainnet Fork
      • ✅FFI
      • ✅Fuzz
      • ✅Invariant Testing - Part 1
      • Invariant Testing - Part 2
      • Invariant Testing - Part 3
      • Differential Test
    • ✅Secureum
      • ✅Epoch 0
        • ✅Slot 1: Ethereum 101
          • ✅Notes
          • ✅Ethereum Whitepaper
          • ✅Extra Study: What happens when you send 1 DAI
          • ✅Quiz
        • ✅Slot 2: Solidity 101
          • ✅Notes
          • ✅OpenZeppelin ERC20
          • ✅OpenZeppelin ERC721
          • ✅OpenZeppelin Ownable
          • ✅OpenZeppelin Pausable
          • ✅OpenZeppelin ReentrancyGuard
          • ✅Quiz
        • ✅Slot 3: Solidity 201
          • ✅Notes
          • ✅OpenZeppelin SafeERC20
          • ✅OpenZeppelin ERC-777
          • ✅OpenZeppelin ERC-1155
          • ✅OpenZeppelin ERC-3156
          • ✅OpenZeppelin - Proxy Upgrade Pattern
          • ✅Quiz
        • ✅Slot 4: Pitfalls and Best Practices 101
          • ✅Notes
          • ✅Intro to Security First Development
          • ✅Quiz
        • ✅Slot 5: Pitfalls and Best Practices 201
          • ✅Notes
          • So you want to use a price oracle
          • The Dangers of Surprising Code
          • ✅Quiz
        • ✅Slot 6: Auditing Techniques & Tools 101
          • ✅Notes
          • ✅Quiz
        • ✅Slot 7: Audit Findings 101
          • Notes
          • ✅Fei Protocol - ConsenSys
          • ✅Uniswap V3 - Trail of Bits
          • ✅Chainlink - Sigma Prime
          • ✅Opyn Gamma - OpenZeppelin
          • ✅Quiz
        • ✅Slot 8: Audit Findings 201
          • Notes
          • 1inch Liquidity - Consensus
          • Original Dollar - Trail of Bits
          • Synthetix EtherCollateral - Sigma Prime
          • Holdefi - OpenZeppelin
          • Quiz
      • ✅Epoch ∞
        • ✅RACE #4 - ERC20 Implementation
        • ✅RACE #5 - ERC1155 Implementation
        • ✅RACE #6 - ERC721 Application
        • ✅RACE #7 - Bored Ape
        • ✅RACE #8 - ERC721 Roles
        • ✅RACE #9 - Proxy
        • ✅RACE #10 - Test Cases
        • ✅RACE #11 - Staking
        • ✅RACE #12 - ERC20 Permit
        • ✅RACE #13 - ERC20 with Callback
        • ✅RACE #14 - Lending
        • ✅RACE #15 - DEX
        • ✅RACE #16 - Flash Loan
        • ✅RACE #17
    • DeFi
      • Glossary
        • TWAP vs. VWAP
        • Tranches
      • DeFi MOOC
        • Lecture 2: Introduction to Blockchain Technologies
        • Lecture 5: DEX
        • Lecture 6: Decentralized Lending
        • Lecture 10: Privacy on the Blockchain
        • Lecture 12: Practical Smart Contract Security
        • Lecture 13: DeFi Security
      • Uniswap V2
      • Compound V3
        • ✅Whitepaper
        • ✅Interacting with Compound
          • ✅Supply and Redeem
          • ✅Borrow and Repay
          • ✅Liquidation
          • ✅Long and Short
        • ✅Interest Model
        • CToken
      • Aave
      • Chainlink
        • ✅Getting Started
        • ✅Data Feeds
        • ✅VRF
      • Optimism
        • Bedrock
      • LayerZero
      • Opensea
        • Seaport
    • EVM
      • ✅Andreas Antonopoulos - The Ethereum Virtual Machine
      • ✅Program The Blockchain - Smart Contract Storage
      • ✅EVM Codes - EVM Playground for Opcodes
      • ✅Fvictorio - EVM Puzzles
      • ✅Daltyboy11 - More EVM Puzzles
      • ✅EVM Through Huff
      • Noxx - EVM Deep Dives
      • ✅Jordan McKinney - EVM Explained
      • Openzepplin - Deconstructing a Solidity Contract
      • Jeancvllr - EVM Assembly
      • Peter Robinson - Solidity to Bytecode, Memory & Storage
      • Marek Kirejczyk - Ethereum Under The Hood
      • ✅Official Solidity Docs
      • Dissecting EVM using go-ethereum Eth client implementation - deliriusz.eth
    • Vulnerabilities
      • Rounding Issues
        • Kyberswap
      • Bridges
      • Governance / Voting Escrows
      • Bizzare Bug Classes
        • TIME - ERC2771Context + Multicall calldata manipulation
    • Fancy Topics
      • Vulnerabilities SoK
        • ✅Demystifying Exploitable Bugs in Smart Contracts
        • Blockchain Hacking Techniques 2022 Top 10 - Todo
      • yAcademy
        • Proxies
          • yAcademy - Proxy Basics
          • yAcademy - Proxies Deep Dive
          • yAcademy - Security Guide to Proxy Vulns
        • defi-fork-bugs
      • Spearbit
        • ✅Community Workshop: Riley Holterhus
        • Economic Security with fmrmf
        • Numerical Analysis for DeFi Audits: A TWAMM Case Study by Kurt Barry
  • Red Teaming
    • ✅Enumeration
      • Service Enumeration
        • SMTP (Port 25)
        • Samba (Port 139, 445)
        • SNMP (Port 161,162,10161,10162)
        • rsync (Port 873)
        • NFS (Port 2049)
        • Apache JServ Protocol (Port 8081)
        • NetBIOS
      • Nmap
      • Gobuster / Feroxbuster / FUFF / Wfuzz
      • Drupal
    • ✅Exploitation
      • Public Exploits
      • PHP Webshells
      • Reverse Shell
      • TTY
      • File Transfer
      • Metasploit
      • Password Spray
    • ✅Buffer Overflow
      • Step 0: Spiking (Optional)
      • Step 1: Fuzzing
      • Step 2: Finding the Offset
      • Step 3: Overwriting the EIP
      • Step 4: Finding Bad Characters
      • Step 5: Finding the Right Module
      • Step 6: Generating Shellcode and Gaining Root
    • ✅Privilege Escalation
      • Linux Privilege Escalation
        • Linux Permissions
        • Manual Enumeration
        • Automated Tools
        • Kernel Exploits
        • Passwords and File Permissions
        • SSH Keys
        • Sudo
        • SUID
        • Capabilities
        • Cron Jobs
        • NFS Root Squashing
        • Docker
        • GNU C Library
        • Exim
        • Linux Privilege Escalation Course Capstone
      • Windows Privilege Escalation
        • Manual Enumeration
        • Automated Tools
        • Kernel Exploits
        • Passwords and Port Forwarding
        • WSL
        • Token Impersonation and Potato Attacks
        • Meterpreter getsystem
        • Runas
        • UAC Bypass
        • Registry
        • Executable Files
        • Startup Applications
        • DLL Hijacking
        • Service Permissions (Paths)
        • CVE-2019-1388
        • HiveNightmare
        • Bypass Space Filter
    • ✅Post Exploitation
      • Linux Post Exploitation
        • Add a User
        • SSH Key
      • Windows Post Exploitation
        • windows-resources
        • Add a User
        • RDP
    • ✅Pivoting
      • Windows: Chisel
      • Linux: sshuttle
    • Active Directory (AD)
      • Initial Compromise
        • HTA Phishing
        • VBA Macro Phishing
        • LLMNR Poisoning
        • SMB Relay
        • GPP / cPassword
      • Domain Enumeration
        • Manual Enumeration
        • PowerView
        • BloodHound
      • Lateral Movement
        • PsExec
        • WMI
        • Runas
        • Pass the Hash
        • Overpass the Hash
        • Pass the Ticket
      • Kerberos
        • Kerberoast
        • AS-REP Roast
      • MS SQL Server
    • Command & Control (C2)
      • Cobalt Strike
        • Bypassing Defences
          • Artifact Kit
          • Resource Kit
          • AMSI Bypass
          • PowerPick
        • Extending Cobalt Strike
          • Elevate Kit
          • Malleable C2 Profile
      • Metasploit
        • Payloads
        • Post Exploitation
        • Automation
      • C2 Development
    • Malware Development
      • "Hot Dropper"
      • PE Format
        • Overview
      • Process Injection
      • Reflective DLL
      • x86 <=> x64
      • Hooking
      • VeraCry
      • Offensive C#
      • AV Evasion
        • AV Evasion with C# and PowerShell
        • AMSI Bypass
  • Cryptography
    • Hash Functions
    • MAC
    • AES
      • Byte at a Time
      • CBC CCA
      • CBC Bit Flipping
      • CBC Padding Oracle
    • Diffie-Hellman
    • RSA
      • Prime Factors
      • Multiple Ciphertexts
      • Low Public Exponent
      • Low Private Exponent
    • ECC
    • Digital Signature
    • JWT
    • PRNG
    • SSL/TLS
    • Research
      • ✅Lattice-based Cryptography (Lattice)
      • Elliptic Curve Cryptography (ECC)
      • Oblivious Transfer (OT)
      • Secure Multi-party Computation (MPC)
      • Learning with Error (LWE)
      • Fully Homomorphic Encryption (FHE)
      • Zero Knowledge Proof (ZKP)
      • Oblivious RAM (ORAM)
  • Computer Science
    • Linux
      • Setup
      • curl
      • Hard Link vs. Symlink
      • Man Page
      • /dev/null
    • Python
      • New Features
      • Operators, Expressions, and Data Manipulation
      • Program Structure and Control Flow
      • Objects, Types, and Protocols
      • Functions 101
      • Generators
      • Classes and Object-Oriented Programming
      • Memory Management
      • Concurrency and Parallelism
        • Multithreading and Thread Safety
        • Asynchronization
        • Multiprocessing
        • Global Interpreter Lock (GIL)
      • Built-in Functions and Standard Library
        • import collections
        • import itertools
        • import sys
        • import re
        • import pickle
        • import json
      • Third-party Library
        • from pwn import *
        • import requests
        • from bs4 import BeautifulSoup
        • from scapy.all import *
        • py2exe
    • HTML, CSS, JavaScript, and React
      • HTML
      • CSS
      • JavaScript
        • var vs. let
        • Objects
        • Arrays
        • Functions
        • Modules
        • Asynchronous JavaScript
      • React
    • Data Structures and Algorithms
      • Binary Search
    • The Linux Programming Interface
      • Processes
        • Memory Allocation
        • The Process API
        • Process Creation
        • Process Termination
        • Monitoring Child Processes
        • Program Execution
      • Signals
      • Threads
        • Thread Synchronization
        • Thread Safety and Pre-Thread Storage
      • IPC
        • Pipes and FIFOs
        • Memory Mappings
        • Virtual Memory Operations
      • Sockets
    • Computer Systems
      • Hexadecimal
      • Signedness
      • Registers
      • Instructions
      • Syscall
      • Process Memory
      • Stack Frame
      • Preemptive Multitasking
      • IPC
      • Threads
    • Databases
      • MySQL
        • Basic Syntax
        • Data Types
        • Modifying Tables
        • Duplicating and Deleting
        • SELECT
        • Transaction
      • GraphQL
    • Distributed Systems
      • Introduction
        • What is a Distributed System?
        • Design Goals
        • Scaling Techniques
        • Types of Distributed Systems
      • Architecture
        • System Architectures
        • Example Architectures
      • Communication
        • Foundations
        • Remote Procedure Call
        • Message-oriented Communication
      • Coordination
        • Clock Synchronization
        • Logical Clock
      • Consistency and Replication
        • Introduction
        • Data-centric Consistency
        • Client-centric Consistency
    • Static Analysis
      • Intermediate Representation
      • Data Flow Analysis
      • Interprocedural Analysis
      • Pointer Analysis
      • Static Analysis for Security
      • Datalog-Based Program Analysis
      • Soundness and Soundiness
      • CFL-Reachability and IFDS
  • Web
    • ✅Prerequisites
      • OWASP Top 10
        • 1. Broken Access Control
        • 2. Cryptographic Failures
        • 3. Injection
        • 4. Insecure Design
        • 5. Security Misconfiguration
        • 6. Vulnerable and Outdated Components
        • 7. Identification and Authentication Failures
        • 8. Software and Data Integrity Failures
        • 9. Security Logging and Monitoring Failures
        • 10. SSRF
      • HTTP
        • HTTP Status Codes
        • HTTP Headers
      • Burp Suite
        • Burp Intruder
        • Burp Extender
        • Burp Collaborator
      • Information Gathering
        • DNS
        • Git
        • Editor
        • Server
      • Bug Bounty Report Writing
    • File Upload
      • Webshell
      • IIS, Nginx, and Apache Vulnerabilities
      • .htaccess (Apache) / web.config (IIS)
      • Alternate Data Stream
      • Code Review: bWAPP Unrestricted File Upload
    • SQL Injection (SQLi)
      • Cheat Sheet
      • UNION Attacks
      • Examining the Database
      • Blind SQL Injection
      • WAF Bypass
      • Out-Of-Band (OOB)
      • Webshell and UDF
      • sqlmap
        • Code Review: Initialization
        • Code Review: tamper
    • Cross-Site Scripting (XSS)
      • Cheat Sheet
      • Reflected XSS
      • Stored XSS
      • DOM-Based XSS
      • XSS Contexts
      • CSP
    • CSRF and SSRF
      • Client-Side Request Forgery (CSRF)
        • XSS vs. CSRF
        • CSRF Tokens and SameSite Cookies
      • Server-Side Request Forgery (SSRF)
        • Attacks
        • Bypassing Restrictions
        • SSRF + Redis
    • XML External Entities (XXE)
    • Insecure Deserialization
      • Python Deserialization
      • PHP Deserialization
      • Java Deserialization
        • Shiro
        • FastJSON
        • WebLogic
    • HTTP Request Smuggling
    • OS Command Injection
      • Whitespace Bypass
      • Blacklist Bypass
      • Blind OS Command Injection
      • Lab 1: HITCON 2015 BabyFirst
      • Lab 2: HITCON 2017 BabyFirst Revenge
      • Lab 3: HITCON 2017 BabyFirst Revenge v2
    • ✅Directory Traversal
    • HTTP Parameter Pollution
    • Server-Side Template Injection (SSTI)
    • LDAP Injection
    • Redis
      • Authentication
      • RCE
      • Mitigations
  • Pwn
    • Linux Exploitation
      • Protections
      • Shellcoding
        • Calling Convention
        • Null-free
        • Reverse Shell
        • ORW
      • ROP
        • Stack Alignment
        • ret2text
        • ret2syscall
        • ret2libc
        • ret2csu
        • BROP
        • SROP
        • Stack Pivot
      • ptmalloc
        • chunks
        • malloc() and free()
        • bins
        • tcache
      • UAF
      • Race Conditions
        • TOCTTOU
        • Dirty Cow
        • Meltdown
        • Spectre
      • Kernel
      • Appendix: Tools
        • socat
        • LibcSearcher-ng
        • OneGadget
    • Windows Exploitation
      • Classic
      • SEH
      • Egghunting
      • Unicode
      • Shellcoding
      • ROP
      • Appendix: Tools
        • ImmunityDbg
        • Mona.py
    • Fuzzing
      • AFL++
        • Quickstart
        • Instrumentation
        • ASAN
        • Code Coverage
        • Dictionary
        • Parallelization
        • Partial Instrumentation
        • QEMU Mode
        • afl-libprotobuf-mutator
      • WinAFL
      • Fuzzilli
  • Reverse
    • Bytecode
      • Python Bytecode
    • 👑Z3 solver
    • angr
      • angr Template
Powered by GitBook
On this page
  • Program Break
  • brk() and sbrk()
  • malloc() and free()
  • Implementation of malloc() and free()
  • Reference

Was this helpful?

  1. Computer Science
  2. The Linux Programming Interface
  3. Processes

Memory Allocation

PreviousProcessesNextThe Process API

Last updated 3 years ago

Was this helpful?

Program Break

A process can allocate memory by increasing the size of the heap, a variable-size segment of contiguous virtual memory that begins just after the uninitialized data segment of a process and grows and shrinks as memory is allocated and freed. The current limit of the heap is referred to as the program break.

Resizing the heap (i.e., allocating or deallocating memory) is actually as simple as telling the kernel to adjust its idea of where the process's program break is. Initially, the program break lies just past the end of the .bss segment, as in the following diagram:

brk() and sbrk()

Traditionally, the UNIX system has provided two syscalls for manipulating the program break, and these are both available on Linux: brk() and sbrk(). Although these syscalls are seldom used directly in programs, understanding them helps clarify how memory allocation works.

Key Ideas:

  • The brk() syscall sets the program break to the location specified by addr. Since virtual memory is allocated in units of pages, addr is effectively rounded to the next page boundary.

  • A call to sbrk() adjusts the program break by adding increament to it. On Linux, sbrk() is a library function implemented on top of brk(). On success, sbrk() returns the previous address of the program break. In other word, if we have increased the program break, the return value points to the start of the newly allocated block of memory.

  • A call to sbrk(0) returns the current setting of the program break without changing it.

malloc() and free()

In general, C programs use the malloc family of functions to allocate and deallocate memory on the heap. These functions offer several advantages over brk() and sbrk(). In particular:

  • They are standardized as part of the C language

  • They are easier to use in threaded programs

  • They provide a simple interface that allows memory to be allocated in small units

  • They allow us to arbitrarily deallocate blocks of memory, which are maintained on a free list and recycled in future calls to allocate memory.

Key Ideas:

  • The malloc(size) function allocate size bytes from the heap and returns a pointer to the start of the newly allocated block of memory. The allocated memory is not initialized.

  • Because malloc() returns void *, we can assign it to any type of C pointers. The block of memory returned by malloc() is always aligned on a byte boundary suitable for efficient access to any type of C data structure. In practice, this means that it is allocated on an 8-byte or 16-byte boundary on most architectures.

  • malloc(0) returns a pointer to a small piece of memory that can (and should) be freed with free().

  • The free() function deallocates the block of memory pointed to by its ptr argument, which should be an address previously returned by malloc().

  • In general, free() doesn't lower the program break, but instead adds the block of memory to a list of free blocks that are recycled by future calls to malloc(). This is done for several reasons:

    • The block of memory being freed is typically somewhere in the middle of the heap, rather than at the end, so that lowering the program break is not possible.

    • It minimizes the number of sbrk() calls that the program must perform. Syscalls have a small but significant overhead.

    • In many cases, lowering the break would not help programs that allocate large amounts of memory, since they typically tend to hold on to allocated memory or repeatedly release and reallocate memory, rather than release it all and then continue to run for an extended period of time.

Implementation of malloc() and free()

Although malloc() and free() provide an interface for allocating memory that is much easier to use than brk() and sbrk(), it is still possible to make various programming errors when using them. Understanding how malloc() and free() are implemented provides us with insights into the causes of these errors and how we can avoid them.

The implementation of malloc() is straightforward. It first scans the list of memory blocks previously released by free() in order to find one whose size is larger than or equal to its requirements. Different strategies may be employed for this scan, depending on the implementation; for example, first-fit or best-fit. If the block is exactly the right size, then it is returned to the caller. If it is larger, then it is split, so that a block of the correct size is returned to the caller and a smaller free block is left on the free list.

If no block on the free list is large enough, then malloc() calls sbrk() to allocate more memory. To reduce the number of calls to sbrk(), rather than allocating exactly the number of bytes required, malloc() increases the program break in larger units (some multiple of the virtual memory page size), putting the excess memory onto the free list.

Looking at the implementation of free(), things start to become more interesting. When free() places a block of memory onto the free list, how does it know what size that block is? This is done via a trick. When malloc() allocates the block, it allocates extra bytes to hold an integer containing the size of the block. This integer is located at the beginning of the block; the address actually returned to the caller points to the location just past this length value, as shown in the following diagram:

When a block is placed on the (doubly linked) free list, free() uses the bytes of the block itself in order to add the block to the list, as shown in the following diagram:

As blocks are deallocated and reallocated over time, the blocks of the free list will become intermingled with blocks of allocated, in-use memory, as shown in the following diagram:

Now consider the fact that C allows us to create pointers to any location in the heap, and modify the locations they point to, including the length, previous free block, and next free block pointers maintained by free() and malloc(). Add this to the preceding description, and we have a fairly combustible mix when it comes to creating obscure programming bugs. For example, if, via a misdirected pointer, we accidentally increase one of the length values preceding an allocated block of memory (metadata corruption), and subsequently deallocate that block, then free() will record the wrong size block of memory on the free list. Subsequently, malloc() may reallocate this block, leading to a scenario where the program has pointers to two blocks of allocated memory that it understands to be distinct, but which actually overlap. Numerous other pictures of what could go wrong can be drawn.

  • After we allocate a block of memory, we should be careful not to touch any bytes outside the range of that block. This could occur, for example, as a result of faulty pointer arithmetic or off-by-one errors in loops updating the contents of a block.

  • It is an error to free the same piece of allocated memory more than once. With glibc on Linux, we often get a segmentation violation (SIGSEGV signal). This is good, because it alerts us that we’ve made a programming error. However, more generally, freeing the same memory twice leads to unpredictable behavior (double free).

  • We should never call free() with a pointer value that wasn’t obtained by a call to one of the functions in the malloc package.

  • If we are writing a long-running program (e.g., a shell or a network daemon process) that repeatedly allocates memory for various purposes, then we should ensure that we deallocate any memory after we have finished using it. Failure to do so means that the heap will steadily grow until we reach the limits of available virtual memory, at which point further attempts to allocate memory fail. Such a condition is known as a memory leak.

Reference

The Linux Programming Interface
The Linux Programming Interface
brk(2) - Linux manual page
brk(2)
malloc(3) - Linux manual page
malloc(3)
Logo
Typical memory layout of a process on Linux /x86-32
brk() and sbrk()
Description and return value
malloc() family
Description
Return value
Memory block returned by malloc()
A block on the free list
Heap containing allocated blocks and a free list